package com.likou.smart;

/**
 * Created by HXT on 2019/7/29.
 */
public class Solution {
    /**
     * 初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。
     * 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。
     * @param n
     * @return
     */
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }

    /**
     * 在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。
     * 一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。
     * 现给定起始字符串start和结束字符串end，请编写代码，
     * 当且仅当存在一系列移动操作使得start可以转换成end时
     * @param start
     * @param end
     * @return
     */
    public boolean canTransform(String start, String end) {
        if(start.length()!=end.length()){
            return false;
        }
        char [] sts = start.toCharArray();
        char [] ends = end.toCharArray();
        int num = 0;
        for (int i=0;i<sts.length;i++){
            if(sts[i]=='R'){
                num++;
            }
            if(ends[i]=='R'){
                if(num>0){
                    num--;
                }else{
                    return false;
                }
            }

            if(ends[i]=='L'){
                num--;
            }
            if(sts[i]=='L'){
                if(num<0){
                    num++;
                }else{
                    return false;
                }
            }
        }
        return num==0;
    }

    /**
     * 三枚石子放置在数轴上，位置分别为 a，b，c。
     每一回合，我们假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。
     当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
     要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]
     * @param b
     * @param c
     * @return
     */
    public int[] numMovesStones(int a, int b, int c) {
        int[] result = new int[2];
        int min = Math.min(Math.min(a,b),c);
        int max = Math.max(c,Math.max(a,b));
        int mid = a+b+c-min-max;
        result[0] = max-min==2?0:(max-mid<3||mid-min<3?1:2);
        result[1]=max-min-2;

        return result;
    }

    /**
     * 给定一个整数矩阵，找出最长递增路径的长度。
     * 对于每个单元格，你可以往上，下，左，右四个方向移动。
     * 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
     * @param matrix 矩阵
     */

    int row, col;
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        row = matrix.length;
        col = matrix[0].length;
        int[][] dp = new int[row][col];
        int res = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(dp[i][j] == 0) {
                    dfs(matrix, i, j, dp, Integer.MIN_VALUE);
                    res = Math.max(res,dp[i][j]);
                }
            }
        }
        return res;
    }

    private int dfs(int[][] matrix, int x, int y, int[][] dp, int prev) {
        if(!inArea(x, y) || matrix[x][y] <= prev) return 0;
        if(dp[x][y] != 0) return dp[x][y];
        int left = dfs(matrix, x, y-1, dp, matrix[x][y]);
        int right = dfs(matrix, x, y+1, dp, matrix[x][y]);
        int up = dfs(matrix, x-1, y, dp, matrix[x][y]);
        int down = dfs(matrix, x+1, y, dp, matrix[x][y]);

        dp[x][y] = Math.max(left, Math.max(right, Math.max(up, down))) + 1;
        return dp[x][y];
    }
    private boolean inArea(int x, int y) {
        return x >=0 && x < row && y >= 0 && y < col;
    }
    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.bulbSwitch(10));
        System.out.println(solution.canTransform("XXXXXLXXXX","LXXXXXXXXX"));
        int[] result = solution.numMovesStones(3,4,5);
        System.out.println(result[0]+"-"+result[1]);
    }
}
